package algorithm.backtracing;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 40. Combination Sum II
 * Leetcode : https://leetcode.com/problems/combination-sum-ii/
 * Diffculty : Medium
 *
 * 给一个数组和一个target，找出数组中和为target的全部唯一组合
 * 要求，每个找出的结果中，数组里的元素之允许使用一次。
 * PS：数组里可能包含重复数字
 *
 * Example:
 * Input: candidates = [10,1,2,7,6,1,5], target = 8
 * Output:
 * [
 *   [1, 7],
 *   [1, 2, 5],
 *   [2, 6],
 *   [1, 1, 6]
 * ]
 *
 *
 * Created by yzy on 2019-04-02 23:51
 */
public class CombinationSumII {

    public static void main(String[] args) {
        int[] cand = new int[]{10,1,2,7,6,1,5};
        int target = 8;
        int[] cand_2 = new int[]{2,5,2,1,2};
        int target_2 = 5;
        List<List<Integer>> result = combinationSum2(cand,target);
        System.out.println(result);

        List<List<Integer>> result_2 = combinationSum2(cand_2,target_2);
        System.out.println(result_2);
    }

    public static List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> tmpList = new ArrayList<>();
        for(int i=0; i<candidates.length; i++){
            int val = candidates[i];
            if(val > target){
                break;
            }
            if(i>0 && val==candidates[i-1]){
                continue;//跳过重复结果
            }
            backtrack(candidates, target, i, result, tmpList);
        }
        return result;
    }


    public static boolean backtrack(int[] candidates, int remainTarget, int index, List<List<Integer>> result, List<Integer> tmpList){
        if(index>=candidates.length || candidates[index] > remainTarget){
            return false;
        }
        int val = candidates[index];
        tmpList.add(val);
        int currRemain = remainTarget - val;
        if(currRemain == 0){
            result.add(new ArrayList<>(tmpList));
            tmpList.remove(tmpList.size()-1);
            return false;
        }

        for(int i=index+1; i<candidates.length; i++){
            int tmpVal = candidates[i];
            if(tmpVal > remainTarget){
                break;
            }
            boolean succ = backtrack(candidates, currRemain, i, result, tmpList);
            if(!succ){
                break;
            }
        }

        tmpList.remove(tmpList.size()-1);
        return true;
    }
}
